﻿#-*- coding: utf-8 -*-
"""
Solveur de grilles de sudoku (backtracking).
Par Guillaume HUYSMANS, 2013.
"""
import time

def ticks():
	"""
	Retourne un nombre de ticks en millisecondes.
	Utile pour chronométrer une fonction sans timeit.
	"""
	return int(round(time.time() * 1000))

class Sudoku(object):
	def __init__(self, filename=""):
		#TODO implémenter la lecture 
		#à partir d'un fichier texte normal
		#(pas question d'utiliser Pickle : illisible)
		self.grid = [ #drôles de motifs :)
			[0, 0, 0, 0, 0, 0, 0, 0, 0],
			[0, 0, 0, 0, 0, 0, 0, 0, 0],
			[0, 0, 0, 0, 0, 0, 0, 0, 0],
			[0, 0, 0, 0, 0, 0, 0, 0, 0],
			[0, 0, 0, 0, 0, 0, 0, 0, 0],
			[0, 0, 0, 0, 0, 0, 0, 0, 0],
			[0, 0, 0, 0, 0, 0, 0, 0, 0],
			[0, 0, 0, 0, 0, 0, 0, 0, 0],
			[0, 0, 0, 0, 0, 0, 0, 0, 0]
		]
		self.grid = [ #exemple pris sur le Net
			[9, 0, 0, 0, 0, 0, 0, 1, 0],
			[0, 0, 7, 9, 1, 0, 6, 5, 0],
			[0, 8, 0, 6, 4, 0, 0, 0, 0],
			[2, 0, 6, 7, 0, 0, 8, 4, 0],
			[5, 0, 3, 1, 0, 6, 9, 0, 2],
			[0, 7, 9, 0, 0, 4, 1, 0, 3],
			[0, 0, 0, 0, 5, 7, 0, 9, 0],
			[0, 9, 2, 0, 6, 8, 5, 0, 0],
			[0, 5, 0, 0, 0, 0, 0, 0, 6]
		]
	
	def save(self, filename):
		"""
		Enregistre la grille sous forme lisible par la classe 
		et par un être humain normalement constitué.
		"""
		#TODO
		raise NotImplemented()
	
	def display(self, x=-1, y=-1):
		"""
		Affiche la grille en mettant en évidence la case (x, y).
		Les cases vides sont représentées par une étoile.
		"""
		j = 0
		for r in self.grid:
			i = 0
			for e in r:
				if x!=-1 and y!=-1:
					f = '!' if (i==x and j==y) else ' '
				else:
					f = ''
				s = str(e) if e!=0 else '*'
				print f+s,
				i += 1
			print ''
			j += 1

	#début des spoilers... ne pas regarder plus loin pour ne pas être influencé.
	###############################################################################

	def check(self):
		"""
		Vérifie la grille passée en paramètre. Aucune optimisation...
		Retourne -1 si incorrecte, 0 si incomplète, 1 si correcte.
		"""
		for x in range(len(self.grid[0])):
			for y in range(len(self.grid)):
				if self.grid[y][x] == 0:
					return 0 #valeur nulle donc pas complète
				elif not self.grid[y][x] in self.get_candidates(x, y):
					return -1 #ça doit être la seule possibilité !
		return 1 #aucune case incorrecte

	def get_candidates(self, x, y):
		"""
		Retourne les valeurs possibles pour une case (x, y) dans la grille.
		La valeur déjà présente en (x, y) est ignorée (utile lors de la vérification).
		Algo : crible, c'est-à-dire qu'on élimine les valeurs non autorisées...
		TODO optimisation possible : passer par un bitmap pour les indiquer en retour.
		"""
		#candidats potentiels : tous
		cl = range(1, 10)
		#toute la colonne
		for py in range(0, len(self.grid)):
			v = self.grid[py][x]
			if (v in cl) and py!=y:
				cl.remove(v)
		#toute la ligne
		for px in range(0, len(self.grid[0])):
			v = self.grid[y][px]
			if (v in cl) and px!=x:
				cl.remove(v)
		#voisins dans la sous-grille
		gx = x / 3 * 3 #on calcule la position
		gy = y / 3 * 3 #... de la sous-grille
		for ox in range(0, 3):
			for oy in range(0, 3):
				px = gx+ox #on calcule une position absolue
				py = gy+oy #... par rapport à la sous-grille
				v = self.grid[py][px]
				if (v in cl) and px!=x and py!=y:
					cl.remove(v)
		#ce qui reste est OK...
		return cl

	def next_empty(self, x, y):
		"""
		Retourne la position de la prochaine case vide.
		Balayage colonne/ligne de G->D et H->B.
		"""
		while self.grid[y][x] != 0:
			x += 1
			if x == len(self.grid[0]):
				x = 0 #retour au début
				y += 1 #ligne suivante
				if y == len(self.grid):
					#on est après la dernière...
					#plus rien à trouver
					return None
		return (x, y) #trouvée !

	def solve(self, x=-1, y=-1):
		"""
		Résout la grille en travaillant sur la case (x, y).
		Algorithme utilisé : backtracking.
		Retourne True si OK, False si impossible.
		"""
		if x==-1: #pas besoin de vérifier l'autre...
			nx = self.next_empty(0, 0) #première case vide
			if nx==None:
				#rien à faire (grille complète)
				return True
			else:
				#résolution (en partant de la bonne case)
				return self.solve(nx[0], nx[1])
		else:
			assert(self.grid[y][x] == 0) #on ne doit surtout pas modifier une donnée !
			cl = self.get_candidates(x, y)
			for c in cl:
				self.grid[y][x] = c #on le place et on voit ce qu'il se passe...
				nx = self.next_empty(x, y) #prochaine case non vide
				if nx==None:
					return True #il n'y en a plus : on a fini !
				elif self.solve(nx[0], nx[1]):
					return True #toutes les suivantes (récursivement...) sont OK !
			self.grid[y][x] = 0 #on la remet à zéro avant de revenir en arrière
			return False #impossible : on a tout essayé...


if __name__=="__main__":
	#Entrée
	g = Sudoku()
	print u"Grille à résoudre"
	g.display()
	#Calculs
	print u"En cours...",
	c = ticks()
	r = g.solve()
	print u"grille", (u"résolue" if r else u"impossible")
	print u"Temps nécessaire :", ticks()-c, "msec"
	#Sortie
	g.display()
	print u"Vérification :", ("ok" if g.check()==1 else "NOOOOOOOOOOOOOON !")